#include <stdio.h>
#include <stdlib.h>

#define V 6  // 图中的顶点数量

// 添加边的函数
void addEdge(int graph[V][V], int src, int dest) {
    graph[src][dest] = 1;  // 从src到dest添加一条边
}

// 计算所有顶点的入度的函数
void findInDegrees(int graph[V][V], int indegree[]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (graph[j][i])
                indegree[i]++;
        }
    }
}

// 执行拓扑排序的函数
void topologicalSort(int graph[V][V]) {
    int indegree[V] = {0};
    findInDegrees(graph, indegree);
    int queue[V], front = 0, rear = -1;
    char result[V]; // 用来存储拓扑排序的结果
    int count = 0;

    // 将所有入度为0的顶点加入队列
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0)
            queue[++rear] = i;
    }

    while (front <= rear) {
        int u = queue[front++]; // 出队
        result[count++] = 'A' + u; // 将索引转换为字符并添加到结果中

        // 减少相邻顶点的入度
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && --indegree[v] == 0)
                queue[++rear] = v;
        }
    }

    if (count != V) {
        printf("图中存在环\n");
        return;
    }

    // 打印拓扑排序的结果
    for (int i = 0; i < V; i++)
        printf("%c ", result[i]);
    printf("\n");
}

int main() {
    int graph[V][V] = {0}; // 初始化邻接矩阵

    // 构建图
    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);

    printf("给定图的拓扑排序:\n");
    topologicalSort(graph);

    return 0;
}
